// 给定一个整数数组nums,找到一个具有最大和的连续子数组（子数组最少包含一个元素）， 返回其最大和
// 解题思路：动态规划
// 假设f(i)表示第i个数结尾的【连续子数组的最大和】，那么f(i) = max(f(i-1) + nums[i], nums[i]) (0 < i <= n-1)
// 即将之前累加和加上当前值与当前值做比较，如果之前累加和加上当前值大于当前值，那么加上当前值，否则f(i) = nums[i]
function maxSubArray(nums) {
    let ans = 0
    let maxAns = nums[0]
    for (let i = 0; i < nums.length; i++) {
        ans = Math.max(nums[i], ans + nums[i])
        maxAns = Math.max(maxAns, ans)        
    }
    return maxAns
}

let nums = [-2,1,-3,4,-1,2,1,-5,4]
console.log(maxSubArray(nums))